﻿using System;
using System.Collections.Generic;
using System.Linq;


namespace ProbabilitySequnce
{
    public class Builder
    {
        public static Random LuckRandom = new Random();
        public static IList<string> RandomSequnce(IList<Option> options)
        {
            var state = InitQueque(options);
            var list = new List<string>(state.Total);
            while (state.Current < state.Total)
            {
                var key = Next(state);
                list.Add(key);
            }
            list.Reverse();
            return list;
        }
        /*
        internal static string Next(IEnumerable<OptionState> states)
        {
            var optionStates = states.Where(it => it.Count > it.Current).ToArray();
            var statesCount = optionStates.Length;
            var count = optionStates.Sum(it => it.Current);
            /*
            var rate = optionStates.Where(it => it.Count > it.Current).Max(it => it.UseRate);
            var source =
                optionStates.Where(it => it.Count > it.Current && it.UseRate == rate)
                    .OrderByDescending(it => it.Count - it.Current)
                    .ThenByDescending(it => it.Count)
                    .FirstOrDefault();
                    if (source == null)
            {
                throw new Exception("没有可生成项");
            }
            source.Current++;
            source.UseRate = source.OriginRate*((source.Count - source.Current)*1M/source.Total) ;
            //source.OriginRate = rate;
            * /
            var sources = optionStates.OrderByDescending(it => it.Count - it.Current).ToArray();

            var r = count%statesCount;
            var source = sources[r];
            source.Current++;
            return source.Key;
        }
        */

        internal static RandomState InitQueque(IList<Option> options)
        {
            if (options.Count < 2)
            {
                throw new Exception("无效的序列");
            }
            var random = new RandomState
            {
                Current = 0,
                Total = options.Sum(it => it.Count),
                Items = new List<IList<Option>>(2)
            };

            var half = random.Total/2;
            if (options.Any(it=>it.Count >= half))
            {
                var op = options.OrderByDescending(it=>it.Count).First(it => it.Count >= half);
                random.Items.Add(new List<Option>
                {
                    new Option {Key = op.Key, Count = half}
                });
                op.Count = op.Count - half;
                if (op.Count == 0)
                {
                    options.Remove(op);
                }
                random.Items.Add(options);
            }
            else
            {
                var op = options.OrderByDescending(it => it.Count).First();
                random.Items.Add(new List<Option> {op});
                options.Remove(op);
                var n = half - op.Count;
                while (n > 0)
                {
                    var item = options.OrderByDescending(it => it.Count).First();
                    if (item.Count > n)
                    {
                       random.Items[0].Add( new Option
                       {
                           Key = item.Key, Count = n
                       });
                        item.Count = item.Count - n;
                        n = 0;
                    }
                    else
                    {
                        random.Items[0].Add(item);
                        options.Remove(item);
                        n = n - item.Count;
                    }
                }
                random.Items.Add(options);
            }
            
            return random;
        }



        internal static string Next(RandomState state)
        {
            var n = state.Items.Count > 1? state.Current%2 : 0;
            var options = state.Items[n];
            Option op;
            if (options.Count > 1)
            {
                var i = LuckRandom.Next(0, options.Count);
                op = options[i];
            }
            else
            {
                op = options[0];
            }
            op.Count--;
            if (op.Count < 1)
            {
                options.Remove(op);
                if (options.Count == 0)
                {
                    state.Items.Remove(options);
                }
            }
            state.Current++;
            return op.Key;
        }
    }
}
